package com.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * 爬楼梯
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 * @author winson
 * @create 2022-04-06 10:36
 */
public class ClimbStairsSolution {

    /**
     * 每次可以爬1或2个台阶
     * 递归求解
     * @param n 1 <= n <= 45
     * @return
     */
    public int climbStairs(int n) {
        if (n < 3) {
            return n;
        }
        return climbStairs(n - 1) + climbStairs(n - 2);
    }

    Map<Integer, Integer> map = new HashMap<>();

    /**
     * 通过变量临时存储前面已计算结果，减少重复计算
     * @param n
     * @return
     */
    public int climbStairsWithRecursion(int n) {
        if (n < 3) {
            map.put(n, n);
            return n;
        }
        int pp = map.containsKey(n - 2) ? map.get(n - 2) : climbStairsWithRecursion(n - 2);
        int p = map.containsKey(n - 1) ? map.get(n - 1) : climbStairsWithRecursion(n - 1);
        map.put(n, pp + p);
        return map.get(n);
    }

    public int climbStairsIteration(int n) {
        /**
         * 迭代计算
         */
        if (n < 3) {
            return n;
        }
        int i = 3;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(1, 1);
        map.put(2, 2);
        while (i <= n) {
            map.put(n, map.get(n - 2) + map.get(n - 1));
            i++;
        }
        return map.get(n);
    }
}
